package com.dy.树.二叉树的锯齿形层次遍历;

import com.dy.树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/*
二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

例如：
给定二叉树 [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回锯齿形层次遍历如下：

[
  [3],
  [20,9],
  [15,7]
]
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root ==null){
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> list = new ArrayList<>();
            while(len>0){
                TreeNode r =queue.peek();
                queue.poll();
                list.add(r.val);
                if(r.left!=null){queue.add(r.left);}
                if(r.right!=null){queue.add(r.right);}
                len--;

            }
            if(res.size()%2==1){
                int start=0;
                int end=list.size()-1;
                while(start<end){
                    int tmp  = list.get(end);
                    list.set(end,list.get(start));
                    list.set(start,tmp);
                    start++;
                    end--;

                }
            }

            res.add(list);
        }
        return  res;
    }


    public List<List<Integer>> zigzagLevelOrder2(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root ==null){
            return res;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int len = queue.size();
            List<Integer> list = new ArrayList<>();
            while(len>0){
                TreeNode r =queue.peek();
                queue.poll();
                if(res.size()%2==0){
                    list.add(r.val);
                }
                else
                    list.add(0,r.val);
                if(r.left!=null){queue.add(r.left);}
                if(r.right!=null){queue.add(r.right);}
                len--;

            }

            res.add(list);
        }
        return  res;
    }
}
